#pragma once
#include <iostream>
#include <assert.h>
#include <vector>
#include "StudentInfo.h"
using namespace std;

// 不同的排序规则
typedef enum {STUID = 0, SCORE = 1, CREDIT = 2, USERNAME = 3} Rule;
//红黑树类型
class RBTree
{
private:
    // 红黑树节点
    typedef enum { RED = 0, BLACK = 1} Color; // 红0 黑1

    //红黑树结点类型
    struct RBTNode
    {
        Color color;    //颜色
        StudentInfo * key;  //关键字
        RBTNode* left;      //左孩子
        RBTNode* right;     //右孩子
        RBTNode* parent;    //父结点
    };
    vector<StudentInfo*>  vStu;
    Rule rule;          // 排序规则
    RBTNode* Nil;       // 外部结点，表示空结点，黑色的
    int total;			// 节点个数
    RBTNode* root;      //根指针

    // si1 > si2的结果
    bool moreThan(StudentInfo* si1, StudentInfo* si2);

    // si1 == si2的结果
    bool equalTo(StudentInfo* si1, StudentInfo* si2);

    // 按从小到大存储学生信息
    void inorder(RBTNode* root);

    //申请结点，将结点的颜色初始化为红色，初始化结点的关键字，其他的初始化为空
    RBTNode* BuyNode(StudentInfo* newValue = nullptr);

    //左转，对z结点左转
    void LeftRotate(RBTNode* z);

    //右转，对z结点进行右转
    void RightRotate(RBTNode* z);

    //插入后的调整函数
    void Insert_Fixup(RBTNode* cur);

    //查找key结点
    RBTNode* Search(RBTNode* root, StudentInfo* dst);

    //将u的子节点指针指向u改变指向v，将v的父节点改变为指向u的父节点
    void Transplant(RBTNode* u, RBTNode* v);

    //找到最左结点(最小)
    RBTNode* Minimum(RBTNode* x);

    //删除红黑树结点z
    void Remove(RBTNode* z);

    //红黑树删除调整
    void Remove_Fixup(RBTNode* x);

    // 销毁红黑树
    void destroy();

    // 递归销毁红黑树
    void Destroy(RBTNode*& root);
public:
    RBTree();
    // 含参构造，传入排序规则（枚举类型）
    RBTree(Rule i);

    //析构函数
    ~RBTree();

    // 重新填充并获取vector
    vector<StudentInfo*> getVec();

    // 插入节点（寻找适当位置插入）
    bool Insert(StudentInfo* newValue);

    //删除key结点(先查找，再调用内部删除)
    bool RemoveNode(StudentInfo* key);

    //中序遍历打印结点详细的结点颜色
    void InOrderPrint();

    //中序遍历打印结点详细的结点颜色
    void InOrderPrint(RBTNode* node);


    // 返回学生信息的位置
    StudentInfo* search(StudentInfo* dst);


};
